<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
 <meta>
  <!-- Stylesheets -->
  <link href="../web.css" type="text/css" rel="stylesheet"></link>
  <link href="../pygmentize.css" type="text/css" rel="stylesheet"></link>
  <title>VLFeat - Documentation - C API</title>
  <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>

  <!-- Scripts-->
  
 </meta>

 <!-- Body Start -->
 <body>
  <div id="header">
   <!-- Google CSE Search Box Begins -->
   <form action="http://www.vlfeat.org/search.html" method="get" id="cse-search-box" enctype="application/x-www-form-urlencoded">
    <div>
     <input type="hidden" name="cx" value="003215582122030917471:oq23albfeam"></input>
     <input type="hidden" name="cof" value="FORID:11"></input>
     <input type="hidden" name="ie" value="UTF-8"></input>
     <input type="text" name="q" size="31"></input>
     <input type="submit" name="sa" value="Search"></input>
    </div>
   </form>
   <script src="http://www.google.com/coop/cse/brand?form=cse-search-box&amp;lang=en" xml:space="preserve" type="text/javascript"></script>
   <!-- Google CSE Search Box Ends -->
   <h1><a shape="rect" href="../index.html" class="plain"><span id="vlfeat">VLFeat</span><span id="dotorg">.org</span></a></h1>
  </div>
  <div id="headbanner">
   Documentation - C API
  </div>
  <div id="pagebody">
   <div id="sidebar"> <!-- Navigation Start -->
    <ul>
<li><a href="../index.html">Home</a>
</li>
<li><a href="../download.html">Download</a>
</li>
<li><a href="../doc.html">Documentation</a>
<ul>
<li><a href="../mdoc/mdoc.html">Matlab API</a>
</li>
<li><a href="index.html" class='active' >C API</a>
</li>
<li><a href="../man/man.html">Man pages</a>
</li>
</ul></li>
<li><a href="../overview/tut.html">Tutorials</a>
</li>
<li><a href="../applications/apps.html">Applications</a>
</li>
</ul>

   </div> <!-- sidebar -->
   <div id="content">
    
    <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>
    <div class="doxygen">
<div>
<!-- Generated by Doxygen 1.7.5.1 -->
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li class="current"><a href="pages.html"><span>Related&#160;Pages</span></a></li>
      <li><a href="annotated.html"><span>Data&#160;Structures</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
    </ul>
  </div>
</div>
<div class="header">
  <div class="headertitle">
<div class="title">K-means clustering </div>  </div>
</div>
<div class="contents">
<div class="textblock"><dl class="author"><dt><b>Author:</b></dt><dd>Andrea Vedaldi</dd></dl>
<p><a class="el" href="kmeans_8h.html">kmeans.h</a> implements a number of algorithm for k-means quantisation. It supports</p>
<ul>
<li>data of type <code>float</code> or <code>double</code>;</li>
<li><em>l1</em> and <em>l2</em> distances;</li>
<li>random selection and <code>k-means++</code> <a class="el" href="citelist.html#CITEREF_arthur07k-means">[2]</a> initialization methods;</li>
<li>the basic Lloyd <a class="el" href="citelist.html#CITEREF_lloyd82least">[5]</a> and the accelerated Elkan <a class="el" href="citelist.html#CITEREF_elkan03using">[4]</a> optimization methods.</li>
</ul>
<h2><a class="anchor" id="kmeans-usage"></a>
Usage</h2>
<p>To use <a class="el" href="kmeans_8h.html">kmeans.h</a> to learn clusters from some training data, instantiate a <a class="el" href="structVlKMeans.html" title="K-means quantizer.">VlKMeans</a> object, set the configuration parameters, initialise the cluster centers, and run the trainig code. For instance, to learn <code>numCenters</code> clusters from <code>numData</code> vectors of dimension <code>dimension</code> and storage type <code>float</code> using L2 distance and at most 100 Lloyd iterations of the Lloyd algorithm use:</p>
<div class="fragment"><pre class="fragment"><span class="preprocessor">#include &lt;<a class="code" href="kmeans_8h.html" title="K-means (K-means clustering)">vl/kmeans.h</a>&gt;</span>

<a class="code" href="kmeans_8h.html#a4c431fed2c5377435e08cbad0040c9f3" title="K-means algorithms.">VlKMeansAlgorithm</a> algorithm = <a class="code" href="kmeans_8h.html#a4c431fed2c5377435e08cbad0040c9f3a19e04f61cc224d6f970a6cba351d6692">VlKMeansLloyd</a> ;
<a class="code" href="mathop_8h.html#aa4cc7d511f708d61bc8fe15c65ad6d74" title="Vector comparison types.">VlVectorComparisonType</a> distance = <a class="code" href="mathop_8h.html#af7397bb42d71000754eafba9458b09acab44b9322465d703274acfa21690de9fd">VlDistanceL2</a> ;
KMeans * kmeans = <a class="code" href="kmeans_8c.html#a868a729d2ea5b9f9fec15a18e0a27a76" title="Create a new KMeans object.">vl_kmeans_new</a> (algorithm, distance, <a class="code" href="generic_8h.html#aa034d0b942f9800b2a02aeb30ff10fa2">VL_TYPE_FLOAT</a>) ;
<a class="code" href="kmeans_8c.html#aad205598b82c6f516e68ed889e3fc19a" title="Seed centers by randomly sampling data.">vl_kmeans_seed_centers_with_rand_data</a> (kmeans, data, dimension, numData, numCenters) ;
<a class="code" href="kmeans_8h.html#a34f80e7e3f4c7213366b88169cc2f70f" title="Set maximum number of iterations.">vl_kmeans_set_max_num_iterations</a> (kmeans, 100) ;
<a class="code" href="kmeans_8c.html#a9fd1885e6b4742a93b4672f56eb9f2ce" title="Refine center locations.">vl_kmeans_refine_centers</a> (kmeans, data, numData) ;
</pre></div><p>Use <a class="el" href="kmeans_8h.html#a02365a4146fabad03f76bb4cdad7cb77" title="Get the number energy of the current fit.">vl_kmeans_get_energy</a> to get the solution energy (or an upper bound for the Elkan algorithm) and <a class="el" href="kmeans_8h.html#a69ecb61159ce9418679f5283c5cb427a" title="Get centers.">vl_kmeans_get_centers</a> to obtain the <code>numCluster</code> cluster centers. Use <a class="el" href="kmeans_8h.html#a3649fe42a94e9b4945511b5665f82355" title="Quantize data.">vl_kmeans_quantize</a> to quantize new data points.</p>
<h3><a class="anchor" id="kmeans-usage-init"></a>
Initialization algorithms</h3>
<p><a class="el" href="kmeans_8h.html">kmeans.h</a> supports the following cluster initialization algorithms:</p>
<ul>
<li><b>Random data points</b> (<a class="el" href="kmeans_8h.html#a087c6c6776ee025e1657b4f724418a61" title="Seed centers by randomly sampling data.">vl_kmeans_seed_centers_with_rand_data</a>) initialize the centers from a random selection of the training data.</li>
<li><b>k-means++</b> (<a class="el" href="kmeans_8h.html#a4e66cedb1d3857d0ffc173ff010c0cbd" title="Seed centers by the KMeans++ algorithm.">vl_kmeans_seed_centers_plus_plus</a>) initialize the centers from a random selection of the training data while attempting to obtain a good coverage of the dataset. This is the strategy from <a class="el" href="citelist.html#CITEREF_arthur07k-means">[2]</a> .</li>
</ul>
<h3><a class="anchor" id="kmeans-usage-optimizers"></a>
Optimization algorithms</h3>
<p><a class="el" href="kmeans_8h.html">kmeans.h</a> supports the following optimization algorithms:</p>
<ul>
<li><b>Lloyd</b> <a class="el" href="citelist.html#CITEREF_lloyd82least">[5]</a> (<a class="el" href="kmeans_8h.html#a4c431fed2c5377435e08cbad0040c9f3a19e04f61cc224d6f970a6cba351d6692">VlKMeansLloyd</a>). This is the standard k-means algorithm, alternating the estimation of the point-to-cluster memebrship and of the cluster centers (means in the Euclidean case). Estimating membership requires computing the distance of each point to all cluster centers, which can be extremely slow.</li>
</ul>
<ul>
<li><b>Elkan</b> <a class="el" href="citelist.html#CITEREF_elkan03using">[4]</a> (<a class="el" href="kmeans_8h.html#a4c431fed2c5377435e08cbad0040c9f3a5f262d513ca0a82ddb577bbe31aa164c">VlKMeansElkan</a>). This is a variation of <a class="el" href="citelist.html#CITEREF_lloyd82least">[5]</a> that uses the triangular inequality to avoid many distance calculations when assigning points to clusters and is typically much faster than <a class="el" href="citelist.html#CITEREF_lloyd82least">[5]</a> . However, it uses storage proportional to the square of the number of clusters, which makes it unpractical for a very large number of clusters.</li>
</ul>
<h2><a class="anchor" id="kmeans-tech"></a>
Technical details</h2>
<p>Given data points <img class="formulaInl" alt="$ x_1, \dots, x_n \in \mathbb{R}^d $" src="form_158.png"/>, k-means searches for <img class="formulaInl" alt="$ k $" src="form_159.png"/> vectors <img class="formulaInl" alt="$ c_1, \dots, c_n \in \mathbb{R}^d $" src="form_160.png"/> (cluster centers) and a function <img class="formulaInl" alt="$ \pi : \{1, \dots, n\} \rightarrow \{1, \dots, k\} $" src="form_161.png"/> (cluster memberships) that minimize the objective:</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ E(c_1,\dots,c_n,\pi) = \sum_{i=1}^n d^2(x_i, c_{\pi(i)}) \]" src="form_162.png"/>
</p>
<p>A simple procedure due to Lloyd <a class="el" href="citelist.html#CITEREF_lloyd82least">[5]</a> to locally optimize this objective alternates estimating the cluster centers and the membeship function. Specifically, given the membership function <img class="formulaInl" alt="$ \pi $" src="form_163.png"/>, the objective can be minimized independently for eac <img class="formulaInl" alt="$ c_k $" src="form_164.png"/> by minimizing</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \sum_{i : \pi(i) = k} d^2(x_i, c_k) \]" src="form_165.png"/>
</p>
<p>For the Euclidean distance, the minimizer is simply the mean of the points assigned to that cluster. For other distances, the minimizer is a generalized average. For instance, for the <img class="formulaInl" alt="$ l^1 $" src="form_166.png"/> distance, this is the median. Assuming that computing the average is linear in the number of points and the data dimension, this step requires <img class="formulaInl" alt="$ O(nd) $" src="form_167.png"/> operations.</p>
<p>Similarly, given the centers <img class="formulaInl" alt="$ c_1, \dots, c_k $" src="form_168.png"/>, the objective can be optimized independently for the membership <img class="formulaInl" alt="$ \pi(i) $" src="form_169.png"/> of each point <img class="formulaInl" alt="$ x_i $" src="form_102.png"/> by minimizing <img class="formulaInl" alt="$ d^2(x_i, c_{\pi(i)}) $" src="form_170.png"/> over <img class="formulaInl" alt="$ \pi(i) \in \{1, \dots, k\} $" src="form_171.png"/>. Assuming that computing a distance is <img class="formulaInl" alt="$ O(d) $" src="form_172.png"/>, this step requires <img class="formulaInl" alt="$ O(ndk) $" src="form_173.png"/> operations and dominates the other.</p>
<p>The algorithm usually starts by initializing the centers from a random selection of the data point.</p>
<h3><a class="anchor" id="kmeans-tech-kmeanspp"></a>
Initialization by k-means++</h3>
<p><a class="el" href="citelist.html#CITEREF_arthur07k-means">[2]</a> proposes a randomized initialization of the centers which improves upon random selection. The first center <img class="formulaInl" alt="$ c_1 $" src="form_174.png"/> is selected at random from the data points <img class="formulaInl" alt="$ x_1, \dots, x_n $" src="form_175.png"/> and the distance from this center to all points <img class="formulaInl" alt="$ d^2(x_i, c_1) $" src="form_176.png"/> is computed. Then the second center <img class="formulaInl" alt="$ c_2 $" src="form_177.png"/> is selected at random from the data points with probability proportional to the distance, and the procedure is repeated using the minimum distance to the centers collected so far.</p>
<h3><a class="anchor" id="kmeans-tech-elkan"></a>
Speeding up by using the triangular inequality</h3>
<p>[3] proposes to use the triangular inequality to avoid most distances calculations when computing point-to-cluster membership and the cluster centers did not change much from the previous iteration.</p>
<p>This uses two key ideas:</p>
<ul>
<li>If a point <img class="formulaInl" alt="$ x_i $" src="form_102.png"/> is very close to its current center <img class="formulaInl" alt="$ c_{\pi(i)} $" src="form_178.png"/> and this center is very far from another center <img class="formulaInl" alt="$ c $" src="form_179.png"/>, then the point cannot be assigned to <img class="formulaInl" alt="$ c $" src="form_179.png"/>. Specifically, if <img class="formulaInl" alt="$ d(x_i, c_{\pi(i)}) \leq d(c_{\pi(i)}, c) / 2 $" src="form_180.png"/>, then also <img class="formulaInl" alt="$ d(x_i, c_{\pi(i)}) \leq d(x_i, c) $" src="form_181.png"/>.</li>
</ul>
<ul>
<li>If a center <img class="formulaInl" alt="$ c $" src="form_179.png"/> is updated to <img class="formulaInl" alt="$ \hat c $" src="form_182.png"/>, then the variation of the distance of the center to any point can be bounded by <img class="formulaInl" alt="$ d(x, c) - d(c, \hat c) \leq d(x, \hat c) \leq d(x,c) + d(c, \hat c) $" src="form_183.png"/>.</li>
</ul>
<p>The first idea is used by keeping track of the inter-center distances and exlcuding reassigments to centers too far away from the current assigned center. The second idea is used by keeping for each point an upper bound to the distance to the currently assigned center and a lower bound to the distance to all the other centers. Unless such bounds do not intersect, then a point need not to be reassigned. See [3] for details. </p>
</div></div>
     <!-- Doc Here -->
    </div>
   
   </div>
   <div class="clear">&nbsp;</div>
  </div> <!-- pagebody -->
  <div id="footer">
   &copy; 2007-12 Andrea Vedaldi and Brian Fulkerson
  </div> <!-- footer -->

  <!-- Google Analytics Begins -->
  <script xml:space="preserve" type="text/javascript">
   //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {
   var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
   document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
   }
   //]]>
  </script>
  <script xml:space="preserve" type="text/javascript">
    //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {

   try {
   var pageTracker = _gat._getTracker("UA-4936091-2");
   pageTracker._trackPageview();
   } catch(err) {}

   }
   //]]>
  </script>
  <!-- Google Analytics Ends -->
 </body>
</html>

 
